﻿using System.Collections.Generic;
using Microsoft.Xna.Framework;
using MyRoguelike.Game;

namespace MyRoguelike.Tools
{
    static class Pathfinding
    {
        /// <summary>
        /// Convert the game map to the pathfinding map
        /// </summary>
        /// <param name="m">Game map</param>
        /// <param name="mapSize">Map size</param>
        /// <returns>Pathfinding map</returns>
        static public int[,] ConvertMap(MapBlock[,] m, Point mapSize)
        {
            int[,] result = new int[mapSize.X,mapSize.Y];

            for (int i = 0; i < mapSize.X; i++)
                for (int j = 0; j < mapSize.Y; j++)
                    result[i, j] = (m[i, j].Type == Level.EMapBlockType.Floor) ? 0 : 1;

            return result;
        }

        /// <summary>
        /// Returns path from 1 point to other point
        /// </summary>
        /// <param name="m">Map (0 - floor, 1 - wall)</param>
        /// <param name="mapSize">Map size</param>
        /// <param name="start">Start point</param>
        /// <param name="finish">Finish point</param>
        /// <returns>Path</returns>
        static public List<Point> Find(int[,] m, Point mapSize, Point start, Point finish)
        {
            int[,] wave = new int[mapSize.X,mapSize.Y];
            for (int i = 0; i < mapSize.X; i++)
                for (int j = 0; j < mapSize.Y; j++)
                    wave[i, j] = -1;

            wave[start.X, start.Y] = 0;

            List<Point> lstOpens = new List<Point>();
            lstOpens.Add(start);

            while (true)
            {
                for (int i = 0; i < lstOpens.Count; i++)
                {
                    Point curr = lstOpens[i];

                    int n = wave[curr.X, curr.Y];

                    int numOfOpens = lstOpens.Count;

                    // Look at left
                    curr.X -= 1;
                    if ((m[curr.X, curr.Y] == 0)
                        && (wave[curr.X, curr.Y] == -1))
                    {
                        lstOpens.Add(new Point(curr.X, curr.Y));
                        wave[curr.X, curr.Y] = n + 1;

                        if (curr == finish) break;
                    }

                    // Look at top
                    curr.X += 1;
                    curr.Y -= 1;
                    if ((m[curr.X, curr.Y] == 0)
                        && (wave[curr.X, curr.Y] == -1))
                    {
                        lstOpens.Add(new Point(curr.X, curr.Y));
                        wave[curr.X, curr.Y] = n + 1;

                        if (curr == finish) break;
                    }

                    // Look at right
                    curr.X += 1;
                    curr.Y += 1;
                    if ((m[curr.X, curr.Y] == 0)
                        && (wave[curr.X, curr.Y] == -1))
                    {
                        lstOpens.Add(new Point(curr.X, curr.Y));
                        wave[curr.X, curr.Y] = n + 1;

                        if (curr == finish) break;
                    }

                    // Look at bottom
                    curr.X -= 1;
                    curr.Y += 1;
                    if ((m[curr.X, curr.Y] == 0)
                        && (wave[curr.X, curr.Y] == -1))
                    {
                        lstOpens.Add(new Point(curr.X, curr.Y));
                        wave[curr.X, curr.Y] = n + 1;

                        if (curr == finish) break;
                    }

                    // If new opens is not added that remove current open
                    if (numOfOpens == lstOpens.Count)
                        lstOpens.RemoveAt(i);
                }

                if (lstOpens.Count == 0) break;
            }

            // If path is not found
            if (wave[finish.X, finish.Y] == -1) return null;
            else
            {
                List<Point> result = new List<Point>();
                result.Add(finish);

                int n = wave[finish.X, finish.Y];

                Point curr = finish;

                while (n != 0)
                {
                    // Look at left
                    curr.X -= 1;
                    if ((wave[curr.X, curr.Y] != -1)
                        && (wave[curr.X, curr.Y] < n))
                    {
                        n = wave[curr.X, curr.Y];
                        result.Add(curr);
                        continue;
                    }

                    // Look at top
                    curr.X += 1;
                    curr.Y -= 1;
                    if ((wave[curr.X, curr.Y] != -1)
                        && (wave[curr.X, curr.Y] < n))
                    {
                        n = wave[curr.X, curr.Y];
                        result.Add(curr);
                        continue;
                    }

                    // Look at right
                    curr.X += 1;
                    curr.Y += 1;
                    if ((wave[curr.X, curr.Y] != -1)
                        && (wave[curr.X, curr.Y] < n))
                    {
                        n = wave[curr.X, curr.Y];
                        result.Add(curr);
                        continue;
                    }

                    // Look at bottom
                    curr.X -= 1;
                    curr.Y += 1;
                    if ((wave[curr.X, curr.Y] != -1)
                        && (wave[curr.X, curr.Y] < n))
                    {
                        n = wave[curr.X, curr.Y];
                        result.Add(curr);
                        continue;
                    }
                }

                result.Reverse();

                return result;
            }
        }
    }
}
